package mo.offer_special;

import mo.common.Node;

public class L029 {

    /**
     * condition1
     *      /
     *     /
     *    /
     *
     *
     * condition2
     *    /|
     *   / |
     *  /  |
     *     |
     *
     * condition3
     *   --------
     *
     *
     *
     * @param head
     * @param insertVal
     * @return
     */
    public Node insert(Node head, int insertVal) {
        Node insert = new Node(insertVal);
        if (head == null) {
            insert.next = insert;
            return insert;
        }
        Node cur = head;
        while (true) {
            if (insertVal >= cur.val && insertVal <= cur.next.val) {
                break;
            }
            if (cur.next.val < cur.val) {
                if (insertVal >= cur.val || insertVal <= cur.next.val) {
                    break;
                }
            }
            if (cur.next == head) {
                break;
            }
            cur = cur.next;
        }
        Node next = cur.next;
        cur.next = insert;
        insert.next = next;
        return head;
    }

}
